package cn.cxq.learning.greedy;

import java.util.*;

/**
 * 情景设置：有很多家商店，
 * 商店里有商品，不同的店可以有多种而且重复的商品，
 * 那么现在需要通过逛最少的商店，以买到这些商店里面所有种类的商品，通过贪心算法实现。
 */
public class ShopProblem {

    private Map<String, Set<String>> shops;
    private Set<String> allGoods;

    /**
     * @param shops 一个二维字符串数组用来存商店名称和商品名称，每一行的第一个元素是商店的名称，其余元素是商品
     */
    public ShopProblem(String[][] shops) {

        this.shops = new HashMap<>();
        this.allGoods = new HashSet<>();

        for (int i = 0; i < shops.length; i++) {

            HashSet<String> goods = new HashSet<>();

            for (int j = 1; j < shops[i].length; j++) {
                goods.add(shops[i][j]);
                this.allGoods.add(shops[i][j]);
            }

            this.shops.put(shops[i][0], goods);
        }
    }

    /**
     * 获取要去的商店名（结果）
     *
     * @return
     */
    public List<String> getShopList() {

        List<String> result = new ArrayList<>();// 用来存需要去的商店名

        HashSet<String> needToBuy = new HashSet<>(); //存任然需要购买的商品
        needToBuy.addAll(this.allGoods);


        while (needToBuy.size() != 0) {

            String maxKey = null; //存储暂时能所比较多未得到的商品的商店指针
            HashSet<String> max = new HashSet<>(); //存储暂时能所比较多未得到的商品清单

            for (String key : this.shops.keySet()) {

                HashSet<String> temp = new HashSet<>();
                temp.addAll(this.shops.get(key));

                temp.retainAll(needToBuy);

                if (maxKey == null) {
                    maxKey = key;
                    max = temp;
                } else {
                    if (temp.size() > max.size()) {
                        maxKey = key;
                        max = temp;
                    }
                }
            }

            result.add(maxKey);
            needToBuy.removeAll(this.shops.get(maxKey));
        }

        return result;
    }

    public Map<String, Set<String>> getShops() {
        return shops;
    }

    public Set<String> getAllGoods() {
        return allGoods;
    }
}
